⟸ Go Back ⟸
Exercise 5 (Homework 4).
(context-free languages, depuration of grammars)

Depuration of grammars

  1. Given a grammar G, describe an algorithm to eliminate \lambda-productions (with only one possible exception) from G (without changing the generated language). Make sure that when G is unambiguous the algorithm described gives an unambiguous grammar. What is the cost of the algorithm?

  2. Given a grammar G, describe an algorithm to eliminate unary production rules from G (without changing the generated language). Make sure that when G is unambiguous the algorithm described gives an unambiguous grammar. What is the cost of the algorithm?

  3. Given a grammar G, describe an algorithm to eliminate useless symbols from G (without changing the generated language). Make sure that when G is unambiguous the algorithm described gives an unambiguous grammar. What is the cost of the algorithm?

  4. Apply the depuration algorithm (remove \lambda-productions, unary productions, unproductive and unreachable symbols) to the following grammars:

    1. \left\{\begin{array}{ccl} S &\to& SS \mid (S) \mid \lambda \end{array}\right.
    2. \left\{\begin{array}{ccl} S &\to& (S)S \mid \lambda \end{array}\right.
    3. \left\{\begin{array}{ccl} S &\to& AA \\ A &\to& AA\mid \lambda \end{array}\right.
    4. \left\{\begin{array}{ccl} S &\to& A \\ A &\to& B \\ B &\to& c \end{array}\right.
    5. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& a\mid \lambda \\ B &\to& b\mid \lambda \end{array}\right.
    6. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& aAb\mid \lambda \\ B &\to& bBc\mid \lambda \end{array}\right.
    7. \left\{\begin{array}{ccl} S &\to& BC \mid \lambda \\ A &\to& aA\mid \lambda \\ B &\to& bB \\ C &\to& c \end{array}\right.
    8. \left\{\begin{array}{ccl} S &\to& X\mid Y \lambda \\ X &\to& Xc\mid A \\ A &\to& aAb\mid \lambda \\ Y &\to& aY \mid B \\ B &\to& bBc \mid \lambda \end{array}\right.
    9. \left\{\begin{array}{ccl} S &\to& A\mid B \mid C \\ A &\to& SaSbS \mid \lambda \\ B &\to& SbSaS \mid \lambda \\ C &\to& Cc\mid \lambda \end{array}\right.